﻿/** ASTARPROGRAMLOGIC CLASS
 * Author: Preeti Francis
 * User ID : pxfranci@scotty.cs.wichita.edu
 * WSU ID: S578F746
 * Course: CS771 
 * Sem: S2014
 * 
 * Description of Class : The AStarProgramLogic contains the A* algorithm program logic. 
 * It is initialized by passing the goal state and initial state to the constructor. 
 * The GetGoal() method formulates the solution and returns the goal node. 
 * Visited nodes : Visited/Explored node states are stored in a hash table (implemented in dotnet using a dictionary). 
 * The hash code for every node's state is generated within the node data structure.
 * Frontier nodes : Frontier nodes are stored in a priority queue implemented using generics with SortedDictionary, List and int.
 * **/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using _8PiecePuzzle.DataStructures;

namespace _8PiecePuzzle.ProgramLogic
{
    public class AStarProgramLogic
    {
        public int[][] GoalState { get; set; }

        public int[][] InitialState { get; set; }

        public string GoalStateHash 
        { 
            get 
            {
                StringBuilder sb = new StringBuilder();
                int n = GoalState.Length;
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        sb.AppendFormat("{0}",GoalState[i][j].ToString());

                    }
                }
                return sb.ToString();
            }
        } 

        public string InitialStateHash
        {
            get
            {
                StringBuilder sb = new StringBuilder();
                int n = InitialState.Length;
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        sb.AppendFormat("{0}", InitialState[i][j].ToString());

                    }
                }
                return sb.ToString();
            }
        }
        

        //Constructor 
        public AStarProgramLogic(int[][] goalState, int[][] initialState)
        {
            GoalState = goalState;

            InitialState = initialState;
        }

        //Returns the goal node if there exists a solution otherwise returns null
        public Node GetGoal()
        {
            Dictionary<string,Node> visitedNodes = new Dictionary<string,Node>();

            PriorityQueue<int, Node> frontierNodes = new PriorityQueue<int, Node>();

            var initialNode = GetInitialStateNode(); 
        
            visitedNodes.Add(initialNode.StateHash, initialNode);

            //Checks if goal state is the initial state
            if (GoalStateHash == InitialStateHash)
            {
                return initialNode;
            }

            var initialChildNodes = Problem.GetChildNodes(initialNode, GoalState);
            
            foreach (var node in initialChildNodes)
            {
                frontierNodes.Enqueue(node.TotalCost, node);
            }

            while (!frontierNodes.IsEmpty)
            {

                //If 1000 nodes are visited then the program assumes that the solution cannot be reached by the algorithm in polynomial time or there is no solution
                if (visitedNodes.Count>1000)
                {
                    return null;
                }

                //Ist level of children
                Node selectedNodeToExpand = frontierNodes.Dequeue();
                
                visitedNodes.Add(selectedNodeToExpand.StateHash, selectedNodeToExpand);

                //Check goal state
                if (Problem.IsGoalState(selectedNodeToExpand.StateHash,GoalStateHash))
                {
                    return selectedNodeToExpand;   
                }

                //Get childNodes and add to frontier
                var childNodes = Problem.GetChildNodes(selectedNodeToExpand, GoalState);
                
                foreach (Node child in childNodes)
                {
                    if (!visitedNodes.ContainsKey(child.StateHash))
                    {
                        bool update = false;
                        Node oldFrontierNode;
                        
                        var frontierSet = frontierNodes.GetEnumerator();

                        // check if the Node already exists in frontier : 
                        // if yes then check if the cost is lesser and then update 
                        // otherwise insert
                        foreach (var frontierNodeSet in frontierSet)
                        {
                            var set = (from n in frontierNodeSet.Value
                                      where n.StateHash == child.StateHash
                                      select n).ToList<Node>();

                            //Check if node exists in frontier
                            if (set.Count()>0)
                            {
                                oldFrontierNode = set[0];
                                //check and update if old node in frontier has higher cost than the one in the current
                                if (oldFrontierNode.TotalCost > child.TotalCost)
                                {
                                    frontierNodes.UpdatePriorityForNode(child.TotalCost, oldFrontierNode.TotalCost, oldFrontierNode, child);
                                }
                                update = true;
                                break;
                            }
                        }
                        //The node does not exist in the frontier at all
                        if (!update)
                        {
                            frontierNodes.Enqueue(child.TotalCost, child);
                        }

                    }
                }
            }

            return null;
        }

        //Returns the initial state node
        private Node GetInitialStateNode()
        {
            int h = Problem.ManhattanCost(InitialState, GoalState);

            Node node = new Node
            {
                Parent = null,
                
                Action = Enum.Action.NoAction,

                PathCost = 0, //Path cost is 0 since it is initial node.

                TotalCost = 0 + h,
                
                State = InitialState
            };

            return node;
        }
    }
}
